/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     left: Node | null
 *     right: Node | null
 *     next: Node | null
 *     constructor(val?: number, left?: Node, right?: Node, next?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */


function connect(root: Node | null): Node | null {
    if(!root) return null;
    root.next = null;
    function traverse(father : Node | null,node: Node | null , tag: boolean) : void {
        if(!node) return ;
        if(tag){
            node.next = father.right;
        }
        else{
            if(father.next){
                node.next = father.next.left
            }
            else{
                node.next = null;
            }
        }
        traverse(node,node.left, true);
        traverse(node,node.right, false);
    }
    traverse(root,root.left,true);
    traverse(root,root.right, false);
    return root;
};

// 执行用时：
// 100 ms
// , 在所有 TypeScript 提交中击败了
// 95.24%
// 的用户
// 内存消耗：
// 44.4 MB
// , 在所有 TypeScript 提交中击败了
// 76.19%
// 的用户